A network security application may monitor network devices on a network to attempt to detect whether any network device has been infected with a malicious application, such as a virus or a malware. Once a malicious application is detected, the network security application may prevent the network application from executing on the network device.
One method for detecting malicious applications employs the use of a relatively large security dataset organized into a base graph having vertices (also called nodes) connected by edges. Because of the relatively large security dataset, the corresponding base graph may also be relatively large. Therefore, to reduce the overall size of a base graph, in order to improve computational efficiency, the base graph may be perturbed. Perturbing a base graph may be accomplished by adding or deleting edges, collapsing vertices into supervertices, or collapsing edges into superedges.
While a perturbed graph can be helpful in improving computational efficiency, a perturbed graph may have less utility than the base graph. Further, it may be difficult to determine just how much utility has been lost between a base graph and a perturbed graph. When the loss in utility between a base graph and a perturbed graph is unknown, using the perturbed graph in a network security application may be problematic because it may not be considered reliable enough to trust with the important task of detecting and preventing malicious applications.
The subject matter claimed herein is not limited to embodiments that solve any disadvantages or that operate only in environments such as those described above. Rather, this background is only provided to illustrate one example technology area where some embodiments described herein may be practiced.